package net.blank.world.aStar.BHeaps
{
	/**
	 * 最小二叉堆
	 * @author blank
	 * 
	 */
	public class BHeapForMin
	{
		/**
		 * 数组,用于保持树的平衡
		 */
		private var nodes:Vector.<BPNode>;
		
		/**
		 * 数组中正在使用的元素数目
		 */
		private var _len:int;
		
		/**
		 * 头节点
		 */
		public var head:BPNode;
		
		/**
		 * 节点对象池(缓存节点)
		 */
		private var $nodePool:Vector.<BPNode>=new Vector.<BPNode>();
		
		/**
		 * 获得一个节点
		 * @return 
		 * 
		 */
		private function getNode(data:*,parent:BPNode):BPNode{
			if($nodePool.length){
				var node:BPNode=$nodePool.pop();
				node.data=data;
				node.parent=parent;
				
				return node;
			}else{
				var newNode:BPNode=new BPNode(data,parent);
				return newNode;
			}
		}
		
		/**
		 * 存储节点
		 * @param node
		 * 
		 */
		private function storeNode(node:BPNode):void{
			node.parent=node.leftChild=node.rightChild=null;
			node.data=null;
			$nodePool.push(node);
		}
		
		/**
		 * 向下修正节点(向树叶方向修正节点)
		 * @param node
		 * @return 
		 * 
		 */
		private function modifyToLeaf(node:BPNode):BPNode{
			var curNodeData:*=node.data;
			var curNodeValue:*=curNodeData.f;
			
			while(true){
				var leftChild:BPNode=node.leftChild;
				var rightChild:BPNode=node.rightChild;
				
				if(rightChild && rightChild.data.f < leftChild.data.f){/*因为是用数组保持树的平衡,所以如果有右子节点,则必须有左子节点*/
					if(curNodeValue > rightChild.data.f){
						node.data=rightChild.data;
						node.data.bstNode=node;
						
						node=rightChild;
					}else{
						break;
					}
				}else if(leftChild && leftChild.data.f < curNodeValue){
					node.data=leftChild.data;
					node.data.bstNode=node;
					
					node=leftChild;
				}else{
					break;
				}
			}
			node.data=curNodeData;
			node.data.bstNode=node;
			
			return node;
		}
		
		/**
		 * 向上修正节点(向树根方向修正节点)
		 * @param node
		 * @return 
		 * 
		 */
		private function modifyToRoot(node:BPNode):BPNode{
			var curNodeData:*=node.data;
			var curNodeValue:*=curNodeData.f;
			
			var parent:BPNode=node.parent;
			while(parent){
				if(curNodeValue < parent.data.f){
					node.data=parent.data;
					node.data.bstNode=node;
					
					node=node.parent;
					parent=node.parent;
				}else{
					break;
				}
			}
			node.data=curNodeData;
			node.data.bstNode=node;
			
			return node;
		}
		
		/**
		 * 修正节点
		 * @param node 节点
		 * @return 
		 * 
		 */
		public function modify(node:BPNode):BPNode{
			if(node.parent && node.parent.data.f > node.data.f){
				return modifyToRoot(node);
			}else{
				return modifyToLeaf(node);
			}
		}
		
		/**
		 * 添加新节点
		 * @param data
		 * @return 
		 * 
		 */
		public function push(data:*):BPNode{
			if(head){
				var parent:BPNode=nodes[_len >> 1];
				var newNode:BPNode=getNode(data,parent);
				newNode.data.bstNode=newNode;
				
				if(!parent.leftChild){
					parent.leftChild=newNode;
				}else{
					parent.rightChild=newNode;
				}
				nodes[_len]=newNode;
				_len++;
				return modifyToRoot(newNode);
			}else{
				nodes[1]=head=getNode(data,null);
				head.data.bstNode=head;
				
				_len=2;
				return head;
			}
		}
		
		/**
		 * 取出最小值
		 * @return 
		 * 
		 */
		public function pop():*{
			var minValue:*=head.data;
			
			var lastNode:BPNode=nodes[--_len];
			if(lastNode != head){
				var parent:BPNode=lastNode.parent;
				if(parent.leftChild == lastNode){
					parent.leftChild=null;
				}else{
					parent.rightChild=null;
				}
				head.data=lastNode.data;
				head.data.bstNode=head;
				
				modifyToLeaf(head);
			}else{
				head=null;
			}
			
			storeNode(nodes[_len]);
			nodes[_len]=null;
			return minValue;
		}
		
		/**
		 * 重置
		 * 
		 */
		public function reset():void{
			for(var i:int=1;i<_len;i++){
				storeNode(nodes[i]);
				nodes[i]=null;
			}
			_len=1;
			
			head=null;
		}
		
		/**
		 * 最小二叉堆
		 * @param cacheSize 
		 * 
		 */
		public function BHeapForMin(cacheSize:int):void{
			nodes=new Vector.<BPNode>(cacheSize,true);
			for(var i:int=0;i<cacheSize;i++){
				$nodePool[i]=new BPNode(null,null);
			}
		}
		
		public function get array():Vector.<BPNode>{
			return nodes;
		}
	}
}